package com.gump.essay.leetcode;

/**
 * @auther zzc
 * @date 2021/4/1 10:45
 */
public class 排序算法 {

    //1 冒泡排序

    /**
     * •基本思想：持续比较相邻的元素。如果第一个比第二个大，就交换他们两个。直到没有任何一对数字需要比较。
     * •冒泡排序最好的时间复杂度为O(n)。冒泡排序的最坏时间复杂度为O(n^2)。因此冒泡排序总的平均时间复杂度为O(n^2)。
     * •算法适用于少量数据的排序，是稳定的排序方法。
     *
     * @param array
     * @return
     */
    public static int[] bubbleSort(int[] array) {
        if (array == null || array.length == 0) {
            return null;
        }
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j + 1] > array[j]) {
                    int tmp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = tmp;
                }
            }
        }
        return array;
    }

    //2 选择排序

    /**
     * •基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
     * •选择排序是不稳定的排序方法。时间复杂度 O(n^2)。
     */
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int min = array[i];
            int minindex = i;
            for (int j = i; j < array.length; j++) {
                if (array[j] < min) {  //选择当前最小的数
                    min = array[j];
                    minindex = j;
                }
            }
            if (i != minindex) { //若i不是当前元素最小的，则和找到的那个元素交换
                array[minindex] = array[i];
                array[i] = min;
            }
        }
    }

    //3 快速排序  递归分治

    /**
     * 时间复杂度最坏是O(n^2),平均时间复杂度为O(nlogn)
     * 快排需要将序列变成两个部分，就是「序列左边全部小于一个数」，「序列右面全部大于一个数」，
     * 然后利用递归的思想再将左序列当成一个完整的序列再进行排序，同样把序列的右侧也当成一个完整的序列进行排序。
     * <p>
     * 其中这个数在这个序列中是可以随机取的，可以取最左边，可以取最右边，当然也可以取随机数。
     * 但是「通常」不优化情况我们取最左边的那个数
     */
    public void quicksort(int[] a, int left, int right) {
        int low = left;
        int high = right;
        //下面两句的顺序一定不能混，否则会产生数组越界！！！very important！！！
        if (low > high)//作为判断是否截止条件
            return;
        int k = a[low];//额外空间k，取最左侧的一个作为衡量，最后要求左侧都比它小，右侧都比它大。
        while (low < high)//这一轮要求把左侧小于a[low],右侧大于a[low]。
        {
            while (low < high && a[high] >= k)//右侧找到第一个小于k的停止
            {
                high--;
            }
            //这样就找到第一个比它小的了
            a[low] = a[high];//放到low位置
            while (low < high && a[low] <= k)//在low往右找到第一个大于k的，放到右侧a[high]位置
            {
                low++;
            }
            a[high] = a[low];
        }
        a[low] = k;//赋值然后左右递归分治求之
        quicksort(a, left, low - 1);
        quicksort(a, low + 1, right);
    }

    //4 直接插入排序

    /**
     * O(n^2)
     * 选取当前位置(当前位置前面已经有序) 目标就是将当前位置数据插入到前面合适位置。
     * 向前枚举或者二分查找，找到待插入的位置。
     * 移动数组，赋值交换，达到插入效果。
     */
    public void insertsort(int a[]) {
        int team = 0;
        for (int i = 1; i < a.length; i++) {
            team = a[i];
            for (int j = i - 1; j >= 0; j--) {
                if (a[j] > team) {
                    a[j + 1] = a[j];
                    a[j] = team;
                } else {
                    break;
                }
            }
        }
    }

    //5

}
